package linear.stack.base;

import linear.linked.base.MyLinked;

/**
 * 链式栈(单向链表)
 *
 * @author yeyangtao created at 10:15 2020/9/22
 */
public class MyLinkedStack<T> implements MyStack<T> {
    //头节点
    private final MyLinked<T> head;
    //尾节点
    private MyLinked<T> curr;
    //栈长度
    private int size = 0;

    public MyLinkedStack() {
        head = new MyLinked<>();
    }

    @Override
    public void push(T x) {
        if (head.getValue() == null) {
            head.setValue(x);
            curr = head;
        } else {
            MyLinked<T> temp = new MyLinked<>(x);
            curr.setNext(temp);
            curr = temp;
        }
        size++;
    }


    public T pop() {
        if (head.getValue() == null) return null;
        T result = curr.getValue();
        //删掉栈顶 快慢指针法
        MyLinked<T> slow = new MyLinked<>();
        slow.setNext(head);
        MyLinked<T> quick = head;
        while (quick.getNext() != null) {
            slow = slow.getNext();
            quick = quick.getNext();
        }
        slow.setNext(null);
        curr = slow;
        size--;
        if (size == 0) {
            head.setValue(null);
        }
        return result;
    }

    public T peek() {
        if (head.getValue() == null) return null;
        return curr.getValue();
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        if (head == null) return "null";
        if (size == 0) return "[]";
        StringBuilder sb = new StringBuilder("[");
        MyLinked<T> temp = head;
        while (temp != null) {
            sb.append(temp.getValue());
            if (temp.getNext() != null)
                sb.append(", ");
            temp = temp.getNext();
        }
        sb.append("]");
        return sb.toString();
    }
}
